// Longest Common Subsequence - * not continues *

#include<iostream>
using namespace std;

char x[] = {'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','x','s'};
char y[] = {'b','x','c','y','d','p','m','n','o','s'};
char ch[20];
int c = 0;
int lcs[1+sizeof(x)/sizeof(char)][1+sizeof(y)/sizeof(char)];
int LCS(int i, int j);
int main()
{
	int i = sizeof(x)/sizeof(char);
	int j = sizeof(y)/sizeof(char);
	
	cout << "\nLCS size is: " << LCS(i,j) << "\n";
	for(int p=0; p<c; p++)
		cout << ":" << ch[p];
	cout << "\n";
	
	return 0;
}

int LCS(int i, int j)
{
	if(lcs[i][j])
	return lcs[i][j];
	
	if(!(i*j))
	return 0;
	
	if(x[i-1] == y[j-1])
	{
		lcs[i][j] = LCS(i-1,j-1) + 1;
		ch[c] = x[i-1];
		c++;
		return lcs[i][j];
	}
	
	lcs[i][j] = max(LCS(i,j-1),LCS(i-1,j));
	return lcs[i][j];
}

